아직 풀지 않은 노노그램 판 (빈칸과 숫자들)이 주어졌을 때,

1. 답이 존재하는지 알아내는 것

2. 답을 알아내는 것

3. 답 하나가 주어졌을 때, 다른 답도 가능한지 알아내는 것

모두 NP-Complete라는걸 증명하는 논문을 발견했어

네덜란드 그로닝겐 대학교의 2017년 석사논문이던데

이게 2017년이나 되서야 증명된 것도 신기하고

=인기가 없다? 라기엔 휴리스틱 알고리즘이나 딥러닝으로 풀게 하는 논문들이 있는데 그런거 쓰려면 NP-Complete라는걸 인용하고 할텐데 말이지

그리고 겨우 석사논문인 것도 신기하네